package targetToOffer.elethDay;

/**
 * @author Godc
 * @description
 */
public class MinNumber {
}
class MinNumberSolution {
    public String minNumber(int[] nums) {
        if(nums.length==0) return "";
        StringBuilder res = new StringBuilder();
        String[] strings = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            strings[i] = String.valueOf(nums[i]);
        }
        quickSort(strings,0,nums.length-1);
        for(String s : strings)
            res.append(s);
        return res.toString();

    }
    public void quickSort(String[] strs, int l, int r){
        if(l >= r) return;
        int i = l, j = r;
        String tmp = strs[i];
        //若拼接字符串 x+y>y+xx + y > y + xx+y>y+x ，则 xxx “大于” yyy ；
        //反之，若 x+y<y+xx + y < y + xx+y<y+x ，则 xxx “小于” yyy ；
        while(i < j) {
            while((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j) j--;
            while((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j) i++;
            tmp = strs[i];
            strs[i] = strs[j];
            strs[j] = tmp;
        }
        strs[i] = strs[l];
        strs[l] = tmp;
        quickSort(strs, l, i - 1);
        quickSort(strs, i + 1, r);
    }
}